/************************************************************************

								Heroes IV
					  Copyright 2001, The 3DO Company

	------------------------------------------------------------------
  						 ai_combat_data_cache.cpp


	$Header: $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "ai_combat_data_cache.h"

#include <algorithm>
#include <set>
#include <math.h>
#include <limits>
#include <vector>
#include "angle.h"
#include "area_effect_point.h"
#include "area_effect_point_ptr.h"
#include "area_effect_point_set.h"
#include "battlefield.h"
#include "can_cast.h"
#include "combat_ai.h"
#include "combat_context.h"
#include "combat_creature.h"
#include "combat_creature_ai_data.h"
#include "combat_footprint.h"
#include "combat_window.h"
#include "creature_ability_properties.h"
#include "creature_traits.h"
#include "creature_type.h"
#include "circle_calculator.h"
#include "difficulty_level.h"
#include "enum_operations.h"
#include "fire_ring.h"
#include "minimum_maximum.h"
#include "obstacle_type.h"
#include "simulated_combat.h"
#include "simulated_combat_creature.h"
#include "skill.h"
#include "spell_properties.h"
#include "stationary_combat_object.h"
#include "threat_footprint.h"

//---------------------------------------------------------------------
// Constructor. Initialize everything to "unknown"
//---------------------------------------------------------------------
t_ai_combat_data_cache::t_ai_combat_data_cache() 
	: m_approximate_battle_length(-1)
{
	m_influence_map_valid = false;
	for (int i = 0; i < 2; i++)
	{
		m_best_offense_bonus[i] = -1;
		m_best_defense_bonus[i] = -1;
		m_casualties_without_spellcasting[i] = -1;
	}
	m_battlefield = 0;
}

void t_ai_combat_data_cache::initialize( t_battlefield& battlefield )
{
	m_battlefield = &battlefield;
	clear_paths();
}

void t_ai_combat_data_cache::clear_paths()
{
	m_attack_angles_map.clear();
	memset( m_retaliation_weight_reduction_valid, 0, sizeof( m_retaliation_weight_reduction_valid ));

	// clear ai data for all creatures
	t_combat_creature_list::iterator	index = m_battlefield->creatures_begin();
	t_combat_creature_list::iterator	end	= m_battlefield->creatures_end();

	for (; index != end; ++index)
		(*index)->clear_ai_variables();
}



//---------------------------------------------------------------------
// Clear data cache for new action. Clear out anything that might have
// changed because of the previous action.
// NOTE: This function is called "too much" -- more than once per action.
// For instance, if a creature has a plague on them, the function is called
// once before the plague takes effect, and once afterwards. However, this
// is actually good -- the second time might change data generated before the
// plague killed a creature.
//---------------------------------------------------------------------
void t_ai_combat_data_cache::new_action(void)
{
	m_approximate_battle_length = -1;
	m_best_damage_map.clear();
	m_best_damage_with_effect_map.clear();
	m_best_damage_without_effect_map.clear();
	m_optimistic_damage_map.clear();
	m_turns_to_combat_map.clear();
	m_creature_interferes_with_list_map.clear();
	m_influence_map_valid = false;
	m_interferes_with_creature_list_map.clear();

	for (int i = 0; i < k_num_area_effect_shapes; i++)
	{
		m_area_effect_point_sets[i].clear();
	}

	for (int i = 0; i < 2; i++)
	{
		m_best_offense_bonus[i] = -1;
		m_best_defense_bonus[i] = -1;
		m_total_combat_value[i] = -1.0;
		m_average_damage_per_hitpoint[i] = -1.0;
		m_casualties_without_spellcasting[i] = -1;
	}
}

t_attack_angle_list const& 
t_ai_combat_data_cache::get_attack_angles( t_combat_creature const&		attacker,
										   t_attackable_object const&	defender,
										   bool							ignore_friendly )
{
	t_attacker_defender_key key;
	
	key.attacker		= &attacker;
	key.defender		= &defender;
	key.ignore_friendly = ignore_friendly;

	t_attack_angles_map::value_type val(key, t_attack_angle_list());

	// Insert or return value
	std::pair<t_attack_angles_map::iterator, bool> insert_return = m_attack_angles_map.insert(val);

	if (insert_return.second)
	{
		// New data inserted, need to actually generate data
		generate_attack_angles( attacker, defender, attacker.get_path_finder( ignore_friendly ), 
								insert_return.first->second);
	}

	return insert_return.first->second;
}

//---------------------------------------------------------------------
// Structures used by t_ai_combat_data_cache::calculate_approximate_battle_length
//---------------------------------------------------------------------
namespace
{
	struct t_simulated_creature_index
	{
		t_combat_creature_ptr			creature;
		t_simulated_combat_creature_ptr simulated_creature;
	};

	typedef std::list<t_simulated_creature_index> t_creature_index_list;
}

static int predict_combat( t_battlefield&			battlefield,
						   bool					attacker_can_cast_spells, 
					       bool					defender_can_cast_spells,
						   t_creature_index_list&	creatures )
{
	t_combat_window*					window = battlefield.get_combat_window();
	t_combat_context&					context = *window->get_context();
	t_simulated_combat					simulation( battlefield.get_armies(), 
													battlefield.get_players(),
													context.get_town(), 
													battlefield.is_sea_battle(),
													battlefield.get_grail_data( false ),
													battlefield.get_grail_data( true ));
	t_simulated_creature_index			item;
	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();

	for (; index != end; ++index)
	{
		if ((*index)->get_number() == 0)
			continue;
		item.creature = *index;
		item.simulated_creature = new t_simulated_combat_creature( *item.creature );
		creatures.push_back( item );
		simulation.add( item.simulated_creature );
	}
	simulation.enable_spellcasting( false, attacker_can_cast_spells );
	simulation.enable_spellcasting( true, defender_can_cast_spells );
	simulation.run();
	return simulation.get_turns();
}	


// -----------------------------------------------------------------------
// void t_ai_combat_data_cache::calculate_approximate_battle_length(void)
// Give a *crude* approximation of how much longer this battle will last,
// in turns, plus several other pieces of data. Results stored in
// t_ai_combat_data_cache member variables
// -----------------------------------------------------------------------
void t_ai_combat_data_cache::calculate_approximate_battle_length(void)
{
	t_creature_index_list				creatures;

	m_approximate_battle_length = predict_combat( *m_battlefield, true, true, creatures );

	t_creature_index_list::iterator creature_index = creatures.begin();
	t_creature_index_list::iterator creatures_end = creatures.end();

	for (; creature_index != creatures_end; ++creature_index)
	{
		t_simulated_creature_index& creature_pair = *creature_index;
		t_combat_creature*			creature = creature_pair.creature;
		t_combat_creature_ai_data&  creature_data = creature->get_ai_data();
		t_simulated_combat_creature& simulated_creature = *creature_pair.simulated_creature;

		creature_data.first_casualty_turn = simulated_creature.get_first_casualty_time();
		creature_data.lifespan = simulated_creature.get_lifespan();
		creature_data.expected_losses = simulated_creature.get_original_number()
									  - simulated_creature.get_number();
	}
}

// -----------------------------------------------------------------------
// void t_ai_combat_data_cache::calculate_approximate_battle_length(void)
// Give a *crude* approximation of how much longer this battle will last,
// in turns, plus several other pieces of data. Results stored in
// t_ai_combat_data_cache member variables
// -----------------------------------------------------------------------
bool t_ai_combat_data_cache::spellcasting_is_worthwhile( bool side )
{
	if (m_casualties_without_spellcasting[side] < 0)
	{
		t_creature_index_list				creatures;

		predict_combat( *m_battlefield, side, !side, creatures );

		t_creature_index_list::iterator creature_index = creatures.begin();
		t_creature_index_list::iterator creatures_end = creatures.end();

		m_casualties_without_spellcasting[side] = 0;
		for (; creature_index != creatures_end; ++creature_index)
		{
			t_simulated_creature_index&		creature_pair = *creature_index;
			t_combat_creature*				creature = creature_pair.creature;
			t_simulated_combat_creature&	simulated_creature = *creature_pair.simulated_creature;

			if (!creature->is_summoned())
				m_casualties_without_spellcasting[side] +=
					simulated_creature.get_original_number() - simulated_creature.get_number();
		}
	}
	return m_casualties_without_spellcasting[side] > 0;
}


int t_ai_combat_data_cache::get_approximate_lifespan(const t_combat_creature &creature)
{
	if (m_approximate_battle_length == -1)
	{
		// compute the expected results from this point
		calculate_approximate_battle_length();
	}

	return creature.get_ai_data().lifespan;
}

int t_ai_combat_data_cache::get_approximate_losses( t_combat_creature const& creature )
{
	if (m_approximate_battle_length == -1)
	{
		// compute the expected results from this point
		calculate_approximate_battle_length();
	}
	return creature.get_ai_data().expected_losses;
}

int t_ai_combat_data_cache::get_approximate_first_casualty_time( t_combat_creature const& creature )
{
	if (m_approximate_battle_length < 0)
		calculate_approximate_battle_length();
	return creature.get_ai_data().first_casualty_turn;
}

// -----------------------------------------------------------------------
// Utility functions for t_ai_combat_data_cache::generate_attack_angles
// -----------------------------------------------------------------------
static void trim( t_attack_angle_list& list, int movement )
{
	if (list.size() < 2)
		return;

	int    i;
	int    last;
	double difference;
	int    closest = 100;
	int    distance;

	for (i = list.size() - 1; i >= 0; i--)
	{
		t_attack_angle& angle = list[i];

		distance = (angle.move_distance - 1) / movement;
		if (distance < closest)
			closest = distance;
	}
	for (i = list.size() - 1; i >= 0; i--)
	{
		t_attack_angle& angle = list[i];

		distance = (angle.move_distance - 1) / movement;
		if (distance > closest)
			list.erase( list.begin() + i );
	}
	for (i = list.size() - 1; i >= 0; i--)
	{
		last = (i + 1) % list.size();

		if (i == last)
			continue;

		t_attack_angle& left = list[i];
		t_attack_angle& right = list[last];

		difference = get_difference( left.attack_angle, right.attack_angle );
		if (difference >= 12 )
			continue;
		if (left.attack_distance < right.attack_distance)
			list.erase( list.begin() + i );
		else
			list.erase( list.begin() + last );
	}
}

void t_ai_combat_data_cache::generate_attack_angles( t_combat_creature const&	attacker, 
													 t_attackable_object const& defender, 
													 t_combat_path_finder&		pathfinder, 
													 t_attack_angle_list&		result)
{
	result.clear();

	if ( attacker.is_active( k_spell_song_of_peace ))
		return;
	if ( defender.is_active( k_spell_sanctuary ))
		return;

	t_battlefield &             battlefield     = *m_battlefield;
	int							attack_distance = attacker.get_attack_range();
	t_combat_object_list		objects = defender.get_objects();
	int							footprint_size;
	t_attack_angle				angle;
	t_map_point_2d				offset;
	t_map_point_2d				new_point;
	t_map_point_2d				attacker_center;
	t_map_point_2d				delta;
	int							distance;
	int							half_attacker_footprint;
	int							half_defender_footprint;
	int							max_distance;
	int							current_footprint;
	int							start_value;
	t_map_point_2d				half_footprint;

	if (defender.is_gate())
		attack_distance = 0;

	t_combat_object_list::iterator object_iterator;

	current_footprint = attacker.get_footprint_size();
	start_value = -current_footprint;
	half_attacker_footprint = attacker.get_half_footprint_size();
	half_footprint.row = half_attacker_footprint;
	half_footprint.column = half_attacker_footprint;
	for (object_iterator = objects.begin(); object_iterator != objects.end(); ++object_iterator)
	{
		t_abstract_combat_object const&	object		= **object_iterator;
		t_map_point_2d					position	= object.get_cell_position();
		t_map_point_2d					center		= object.get_footprint_center();

		footprint_size	= object.get_footprint_size() + attack_distance * 2 + 1;
		half_defender_footprint = object.get_half_footprint_size();
		max_distance = half_attacker_footprint + half_defender_footprint 
					 + (attack_distance << k_battlefield_subcell_shift)
					 + (k_battlefield_subcells_per_cell >> 1);
		// check if target is in tower.  If so, we can attack if we can
		// touch the tower.
		if (defender.is_in_tower())
		{
			t_battlefield_cell const&   cell = battlefield.get_cell( center >> k_battlefield_subcell_shift );
			t_stationary_combat_object* tower = cell.get_obstacle( k_obstacle_castle_tower );

			assert( tower != 0 );
			assert( tower->get_obstacle_type() == k_obstacle_castle_tower );
			footprint_size += tower->get_footprint_size() - object.get_footprint_size();
			max_distance += tower->get_half_footprint_size() - half_defender_footprint;
		}
		// check special case: attacking from inside tower.
		if (attacker.is_in_tower())
		{
			attacker_center = attacker.get_footprint_center();

			t_stationary_combat_object* tower = attacker.get_tower();
			t_map_point_2d              current_point;

			assert( tower != 0 );
			assert( tower->get_obstacle_type() == k_obstacle_castle_tower );
			delta = center - attacker_center;
			distance = delta.row * delta.row + delta.column * delta.column;
			distance = sqrt( (double)distance ) + 0.5;
			distance -= tower->get_half_footprint_size() - half_attacker_footprint;
			if (distance <= max_distance)
			{
				angle.point = attacker.get_cell_position();
				angle.attack_angle = get_angle( delta );
				angle.attack_distance = distance;
				angle.move_distance = 0;
				result.push_back( angle );
			}
		}
		position.row -= attack_distance;
		position.column -= attack_distance;
		for (offset.row = start_value; offset.row < footprint_size; offset.row++)
		{
			for (offset.column = start_value; offset.column < footprint_size; offset.column++)
			{
				new_point = position + offset;
				if (!battlefield.is_valid( new_point ))
					continue;

				t_combat_path_data const& path_data = pathfinder.get_data( new_point );

				if (!path_data.visited || path_data.blocked)
					continue;

				attacker_center = (new_point << k_battlefield_subcell_shift) + half_footprint;
				delta = center - attacker_center;
				distance = delta.row * delta.row + delta.column * delta.column;
				distance = sqrt( (double)distance ) + 0.5;
				if (distance > max_distance)
					continue;
				angle.point = new_point;
				angle.attack_angle = get_angle( delta );
				angle.attack_distance = distance;
				angle.move_distance = path_data.move_cost;
				result.push_back( angle );
			}
		}
	}
	std::sort( result.begin(), result.end() );
	trim( result, attacker.get_combat_movement() );
}



// Get ranged units this unit is interfering with
const t_combat_creature_list &t_ai_combat_data_cache::get_creature_interferes_with_list( t_combat_creature const& creature)
{
	t_creature_creature_list_map::value_type val(&creature, t_combat_creature_list());
	
	// Insert or return value
	std::pair<t_creature_creature_list_map::iterator, bool> insert_return = m_creature_interferes_with_list_map.insert(val);

	if (insert_return.second)
	{
		// New data inserted, need to actually generate data
		creature.get_interfere_with_list( insert_return.first->second );
	}

	return insert_return.first->second;
}

// Get units which are interfering with this unit
const t_combat_creature_list &t_ai_combat_data_cache::get_interferes_with_creature_list( t_combat_creature const& creature)
{
	t_creature_creature_list_map::value_type val(&creature, t_combat_creature_list());
	
	// Insert or return value
	std::pair<t_creature_creature_list_map::iterator, bool> insert_return = m_interferes_with_creature_list_map.insert(val);

	if (insert_return.second)
	{
		// New data inserted, need to actually generate data
		creature.get_interfered_by_list( insert_return.first->second );
	}

	return insert_return.first->second;
}


// Internal functions for generate_base_area_effect_point_set()
namespace
{
	// Generate the list of points that an area-effect attack of
	// shape k_area_effect_shape_<radius>_circle could be aimed at
	// and affect the given creature. Does *not* include the 
	// center point of the creature itself
	class t_circle_point_generator 
	{
		public:
			t_circle_point_generator( t_battlefield& battlefield,
				                      const t_combat_creature &creature, int diameter);

			bool get_next_point(t_map_point_2d &next);
			
		private:
			t_battlefield&		m_battlefield;
			t_ring_calculator   m_calculator;

	};

	inline
	t_circle_point_generator::t_circle_point_generator( t_battlefield& battlefield,
														const t_combat_creature &creature, 
													    int diameter)
		: m_calculator(creature.get_footprint_center() >> (k_battlefield_subcell_shift - 1),
					   (creature.get_footprint_size() << 1) - 3,
		               ((creature.get_footprint_size() + diameter) << 1) + 4),
		  m_battlefield( battlefield )
	{
		;
	}

	inline
	bool t_circle_point_generator::get_next_point(t_map_point_2d &next)
	{
		// Note that calculator is working in HALF cell units, 
		// Ignore any points which don't come out even
		do
		{
			do
			{
				if (!m_calculator.get_next_point(next))
				{
					return false;
				}
			}
			while ((next.row & 0x1) || (next.column & 0x1));

			next >>= 1; // Divide by 1/2
		}
		while (!m_battlefield.is_valid(next));

		return true;
	}

	// Add the creatures touched by a circle with given radius around a 
	// given point. All units are subcell units
	void add_creatures_for_point( t_battlefield& battlefield, t_map_point_2d	center,
								  int radius, t_area_effect_point &point)
	{
		t_combat_creature_list affected_list = battlefield.get_area_targets(center, radius);
		t_combat_creature_list::iterator affected_index;
		t_combat_creature_list::iterator affected_end = affected_list.end();
		
		// find who is actually in the area
		for (affected_index = affected_list.begin(); affected_index != affected_end; affected_index++)
		{
			point.add_creature( *affected_index );
		}
	}
}

// The function responsible for generating lists of which creatures will be
// affected by an area attack at the various legal points
void t_ai_combat_data_cache::generate_base_area_effect_point_set(t_area_effect_shape shape, t_area_effect_point_set &result)
{
	result.clear();

	t_battlefield &battlefield = *m_battlefield;

	int diameter;

	switch(shape)
	{
		case k_area_effect_shape_3_headed:
		case k_area_effect_shape_hydra:
			// Not implemented
			return;

		case k_area_effect_shape_firering:
			diameter = 9; // Diameter if not cast on a creature
			break;

		case k_area_effect_shape_4_circle:
			diameter = 8;
			break;

		case k_area_effect_shape_5_circle:
			diameter = 10;
			break;

		case k_area_effect_shape_7_circle:
			diameter = 14;
			break;

		default:
			assert(false);
			return;
	}

	const int map_size = battlefield.get_size();

	std::vector<bool> visited_points;

	// Each point [row, column] is visited if 
	// visited_points[(row * map_size) + column]
	// is true
	visited_points.resize(map_size * map_size, false);

	t_combat_creature_list::iterator creature_iterator;

	// Do "attack a creature"
	for (creature_iterator = battlefield.creatures_begin(); creature_iterator != battlefield.creatures_end(); creature_iterator++)
	{		
		const t_combat_creature *creature = *creature_iterator;

		if (creature->get_number() <= 0)
			continue;

		if (creature->is_active( k_spell_sanctuary ))
			continue;

		t_map_point_2d           creature_point = creature->get_cell_position();

		// Add all points in the creature's footprint into the "visited_points" set
		// so that we don't try to attack a point which is in a creature's footprint
		const t_combat_footprint &footprint = creature->get_footprint();
		const int				 *footprint_ptr = footprint.get();
		const int                 footprint_size = footprint.get_size();
		t_map_point_2d            offset;

		for (offset.row = 0; offset.row < footprint_size; offset.row++)
		{
			for (offset.column = 0; offset.column < footprint_size; offset.column++)
			{
				if (!(*(footprint_ptr++)))
					continue;
		
				t_map_point_2d footprint_point = creature_point + offset;

				if (footprint_point.row < map_size && footprint_point.column < map_size)
				{
					visited_points[(footprint_point.row * map_size) + footprint_point.column] = true;
				}
			}
		}

		if (shape == k_area_effect_shape_firering)
		{
			// Only one point -- the center -- is legal target within creature
			t_combat_creature_list affected_list;

			t_fire_ring::get_basic_target_list(*m_battlefield, creature, affected_list);

			if (!affected_list.empty())
			{
				t_area_effect_point_ptr area_effect_point = new t_area_effect_point;
	
				// Transfer from list to set
				t_combat_creature_list::iterator it;
				for (it = affected_list.begin(); it != affected_list.end(); it++)
				{
					area_effect_point->add_creature(*it);
				}

				// Add into the area_effect_set
				std::pair<t_area_effect_point_set::iterator, bool> insert_return = result.insert(area_effect_point);

				// Use the center of the creature to mean "cast on the creature"
				(*insert_return.first)->add_point(creature->get_footprint_center() >> k_battlefield_subcell_shift);
			}
		}
		else
		{
			// Any of the "outside squares" on a creature can be a potential target
			// from some direction (cells that touch, in some direction or another,
			// a non-footprint cell)
			for (offset.row = 0; offset.row < footprint_size; offset.row++)
			{
				for (offset.column = 0; offset.column < footprint_size; offset.column++)
				{
					bool outer_cell;

					if (!footprint[offset.row][offset.column])
					{
						outer_cell = false;
					}
					else if (   offset.row    == 0 || offset.row    == (footprint_size - 1)
							 || offset.column == 0 || offset.column == (footprint_size - 1))
					{
						outer_cell = true;
					}
					else
					{
						// Any of the eight directions clear?
						outer_cell =    !footprint[offset.row - 1][offset.column - 1]
									 || !footprint[offset.row - 1][offset.column    ]
									 || !footprint[offset.row - 1][offset.column + 1]
									 || !footprint[offset.row    ][offset.column - 1]
									 || !footprint[offset.row    ][offset.column + 1]
									 || !footprint[offset.row + 1][offset.column - 1]
									 || !footprint[offset.row + 1][offset.column    ]
									 || !footprint[offset.row + 1][offset.column + 1];
					}
					
					if (outer_cell)
					{
						t_area_effect_point_ptr area_effect_point = new t_area_effect_point;
						t_map_point_2d point = creature_point + offset;
		
						add_creatures_for_point( *m_battlefield, get_cell_center(point),
												 diameter << (k_battlefield_subcell_shift - 1), 
												 *area_effect_point);

						assert(!area_effect_point->get_affected_list().empty());

						// Add into the area_effect_set
						std::pair<t_area_effect_point_set::iterator, bool> result_insert_return = result.insert(area_effect_point);

						(*result_insert_return.first)->add_point(point);
					}
				}
			}
		}
	}


	// Do points around creatures where the creature would still be affected
	for (creature_iterator = battlefield.creatures_begin(); creature_iterator != battlefield.creatures_end(); creature_iterator++)
	{
		const t_combat_creature &creature = **creature_iterator;

		// Generate points around creature where spell could be targeted
		t_circle_point_generator point_generator( *m_battlefield, creature, diameter);
		t_map_point_2d point;
		while (point_generator.get_next_point(point))
		{
			// Check if point already visited. If not, insert it
			assert(point.row < map_size && point.column < map_size);

			int visited_points_index = (point.row * map_size) + point.column;

			if (visited_points[visited_points_index])
				continue;

			visited_points[visited_points_index] = true;

			t_area_effect_point_ptr area_effect_point = new t_area_effect_point;

			if (shape == k_area_effect_shape_firering)
			{
				t_combat_creature_list affected_list;

				t_fire_ring::get_basic_target_list( *m_battlefield, point, affected_list);

				// Transfer from list to set
				t_combat_creature_list::iterator it;
				for (it = affected_list.begin(); it != affected_list.end(); it++)
				{
					area_effect_point->add_creature(*it);
				}
			}
			else
			{
				add_creatures_for_point( *m_battlefield, get_cell_center(point), 
										 diameter << (k_battlefield_subcell_shift - 1),
										 *area_effect_point);
			}

			if (area_effect_point->get_affected_list().empty())
				continue;

			// Add into the area_effect_set
			std::pair<t_area_effect_point_set::iterator, bool> result_insert_return = result.insert(area_effect_point);

			(*result_insert_return.first)->add_point(point);
		}
	}

	assert(!result.empty());
}

void t_ai_combat_data_cache::generate_total_combat_values(void)
{
	m_total_combat_value[false] = 0.0;
	m_total_combat_value[true] = 0.0;

	t_combat_creature_list::iterator creature_index, creature_end;

	creature_end = m_battlefield->creatures_end();

	for (creature_index = m_battlefield->creatures_begin(); creature_index != creature_end; 
		 creature_index++)
	{
		m_total_combat_value[(*creature_index)->get_controller()] += (*creature_index)->get_combat_value();
	}
}

// ---------------------------------------------------------------
// get or generate a path map based on a footprint and combat obstacles
// ---------------------------------------------------------------
t_combat_path_map const& t_ai_combat_data_cache::get_obstacle_map( int size )
{
	t_path_map_keyed_array::iterator result = m_path_maps.find( size );

	if (result == m_path_maps.end())
	{
		t_battlefield&		battlefield = *m_battlefield;
		t_combat_path_map	path_map( battlefield.get_size() );
		t_combat_footprint	footprint = get_combat_footprint( size );

		if (m_obstacle_map_ptr.get() == 0)
		{
			t_combat_path_blockage	blockage;
			int						map_size = battlefield.get_size();

			blockage.blocked = false;
			blockage.in_tower = false;
			blockage.has_wall = false;

			m_obstacle_map_ptr.reset( new t_combat_path_blockage_map( map_size, 
								      k_battlefield_cell_height, 
								      k_battlefield_logical_view_size, blockage ));
			m_obstacle_map_ptr->mark_obstacles( battlefield );
		}
		path_map.init_map( battlefield, *m_obstacle_map_ptr, footprint );
		result = m_path_maps.insert( std::make_pair( size, path_map ) ).first;
	}
	return result->second;
}

// ---------------------------------------------------------------
// get or generate a terrain map based on a footprint size
// ---------------------------------------------------------------
t_combat_terrain_map const& t_ai_combat_data_cache::get_terrain_map( int footprint_size )
{
	t_terrain_keyed_array::iterator result = m_terrain_maps.find( footprint_size );

	if (result == m_terrain_maps.end())
	{
		t_combat_terrain_map map( footprint_size, *m_battlefield );

		result = m_terrain_maps.insert( std::make_pair(footprint_size, map) ).first;
	}
	return result->second;
}

// ---------------------------------------------------------------
// get time for a creature to attack a target
// ---------------------------------------------------------------
bool t_ai_combat_data_cache::get_attack_time( t_combat_creature const&	attacker,
											  t_combat_creature const&	target,
											  int&						turns )
{
	t_attack_angle_list const& attack_angles = get_attack_angles( attacker, target );

	if (attack_angles.empty())
		return false;

	int				combat_movement = attacker.get_combat_movement();
	t_attack_angle	attack_angle = attack_angles.front();

	turns = (attack_angle.move_distance + combat_movement - 1) / combat_movement;
	if (turns < 1)
		turns = 1;
	return true;
}

// ---------------------------------------------------------------
// get amount to reduce retaliation weights
// ---------------------------------------------------------------
double t_ai_combat_data_cache::get_retaliation_weight_reduction( t_combat_creature const& target,
																 bool					  ranged )
{
	if (!m_retaliation_weight_reduction_valid[target.belongs_to_defender()][ranged])
		compute_retaliation_weight_reductions( target.belongs_to_defender(), ranged );
	return target.get_retaliation_weight_reduction( ranged );
}

// ---------------------------------------------------------------
// get lowest possible retaliation
// ---------------------------------------------------------------
static double get_lowest_melee_retaliation( t_battlefield&				battlefield,
										    t_combat_creature const&	attacker,
											t_combat_creature_list&		targets,
											t_ai_combat_data_cache&		data )
{
	t_combat_creature_list::iterator	target_index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					target;
	double								weight;
	double								lowest;
	int									turns;
	int									closest;
	bool								side = attacker.belongs_to_defender();

	for (target_index = battlefield.creatures_begin(); target_index != end; ++target_index)
	{
		target = *target_index;
		if (target->belongs_to_defender() == side)
			continue;
		if (target->get_number() == 0)
			continue;
		if (!data.get_attack_time( attacker, *target, turns ))
			continue;
		if (!targets.empty() && turns > closest)
			continue;
		if (targets.empty() || turns < closest)
		{
			targets.clear();
			closest = turns;
		}
		weight = 0.0;
		if (target->can_retaliate( attacker, false, turns ))
		{
			t_attack_angle_list const& attack_angles = data.get_attack_angles( attacker, *target );

			if (!attack_angles.empty())
			{
				t_attack_angle		attack_angle = *attack_angles.get_farthest();
				int					distance = attack_angle.move_distance;
				int					combat_movement = attacker.get_combat_movement();
				t_creature_int_map	damage_map;

				if (distance > combat_movement)
					distance = combat_movement;
				attacker.get_melee_exchange_effect( *target, distance, damage_map, attack_angle, 
													target->get_cell_position(), true );
				weight = attacker.get_ai_value( damage_map[&attacker] );
			}
		}
		if (targets.empty() || weight <	lowest)
			lowest = weight;
		targets.push_back( target );
	}
	return lowest;
}

// ---------------------------------------------------------------
// get lowest possible retaliation
// ---------------------------------------------------------------
static double get_lowest_ranged_retaliation( t_battlefield&				battlefield,
											 t_combat_creature const&	attacker,
											 t_combat_creature_list&	targets )
{
	t_combat_creature_list::iterator	target_index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					target;
	double								weight;
	double								lowest;
	bool								side = attacker.belongs_to_defender();

	for (; target_index != end; ++target_index)
	{
		target = *target_index;
		if (target->belongs_to_defender() == side)
			continue;
		if (target->get_number() == 0)
			continue;
		if (!battlefield.can_see( attacker, *target ))
			continue;
		if (!target->can_retaliate( attacker, true ))
			weight = 0.0;
		else
		{
			int					retaliation;
			t_combat_creature*	retaliation_target;

			attacker.project_ranged_damage( *target, retaliation, retaliation_target );
			weight = retaliation_target->get_ai_value( retaliation );
		}
		if (targets.empty() || weight <	lowest)
			lowest = weight;
		targets.push_back( target );
	}
	return lowest;
}



// ---------------------------------------------------------------
// compute reductions to retaliation weights
//
// for each friendly creature
//		examine closest melee targets
//		determine lowest retaliation damage
//		mark each reachable enemy with weight of retaliation, if >= last value
//
// allows creatures to take into account multiple creature attacks
// when computing cost of retaliations
//---------------------------------------------------------------
void t_ai_combat_data_cache::compute_retaliation_weight_reductions( bool side, bool ranged )
{
	if (m_retaliation_weight_reduction_valid[side][ranged])
		return;

	m_retaliation_weight_reduction_valid[side][ranged] = true;

	t_battlefield&						battlefield = *m_battlefield;
	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	target_index;
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	double								lowest;
	t_combat_creature*					acting_creature;
	t_combat_creature*					attacker;
	t_combat_creature*					target;
 
	acting_creature = battlefield.get_acting_creature();
	for (index = battlefield.creatures_begin(); index != end; ++index)
	{
		target = *index;
		if (target->belongs_to_defender() == side)
			target->set_retaliation_weight_reduction( ranged, 0.0 );
			continue;
	}
	if (battlefield.get_difficulty() < k_difficulty_normal)
		return;
	for (index = battlefield.creatures_begin(); index != end; ++index)
	{
		attacker = *index;
		if (attacker->belongs_to_defender() == side)
			continue;
		if (attacker == acting_creature)
			continue;
		if (attacker->get_number() == 0)
			continue;
		if (attacker->is_incapacitated())
			continue;
		if (attacker->is_active( k_spell_song_of_peace ))
			continue;

		t_combat_creature_list	targets;

		if (ranged)
		{
			if (attacker->has_nonmissile_damage_spells())
				continue;
			if (!attacker->has_missile_spells() && !battlefield.can_shoot( *attacker ))
				continue;
			lowest = get_lowest_ranged_retaliation( *m_battlefield, *attacker, targets );
		}
		else
		{
			if (attacker->has_damage_spells() || battlefield.can_shoot( *attacker ))
				continue;
			lowest = get_lowest_melee_retaliation( battlefield, *attacker, targets, *this );
		}
		for (target_index = targets.begin(); target_index != targets.end(); ++target_index)
		{
			target = *target_index;
			if (lowest > target->get_retaliation_weight_reduction( ranged ))
				target->set_retaliation_weight_reduction( ranged, lowest );
		}
	}
}


// ---------------------------------------------------------------
// mark areas where enemies which cannot attack this turn can melee
// ---------------------------------------------------------------
static void mark_melee_ranges( t_battlefield&			battlefield,
							   t_influence_map&			map, 
							   t_combat_creature const& current_creature,
							   t_ai_combat_data_cache&	data )
{
	t_combat_creature const*				enemy;
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	double									weight;
	bool									retaliate;
	t_attack_angle							attack_angle;

	for (; index != end; ++index)
	{
		enemy = *index;
		if (enemy->get_controller() == current_creature.get_controller())
			continue;
		if (!enemy->is_awake())
			continue;
		if (enemy->is_active( k_spell_song_of_peace ))
			continue;
		// check if we'll probably move first.
		if (enemy->has_moved() && current_creature.get_speed() > enemy->get_speed())
			continue;
		if (threatens_enemies( *enemy ))
			continue;

		t_creature_int_map damage_map;

		retaliate = current_creature.can_retaliate( *enemy, false, 2 );
		attack_angle.point = enemy->get_cell_position();
		attack_angle.attack_angle = 0;
		enemy->get_melee_exchange_effect( current_creature, enemy->get_combat_movement(), damage_map,
										  attack_angle, current_creature.get_cell_position(), 
										  retaliate );
		// use just these 2 - ignore damage inflicted on other creatures
		weight = enemy->get_ai_value( damage_map[enemy] ) 
				 - current_creature.get_ai_value( damage_map[&current_creature] );
		if (weight >= 0.0)
			continue;

		// mark all attackable points with the weight
		t_map_point_2d				point;
		int							row_size;
		double*						dest;
		t_combat_path_data const*	path;

		point.row = map.get_size();
		while (point.row--)
		{
			point.column = map.get_row_start( point.row );
			row_size = map.get_row_size( point.row );
			dest = &map.get( point );
			path = &enemy->get_path_finder().get_data( point );
			while (row_size--)
			{
				if (path->attackable)
					*dest += weight;
				dest++;
				path++;
			}
		}
	}
}

// ---------------------------------------------------------------
// get lowest value in a footprint in the influence map
// ---------------------------------------------------------------
static double get_lowest_value( t_influence_map const&	map, t_combat_footprint const& footprint,
								t_map_point_2d const&	point )
{
	int				footprint_size = footprint.get_size();
	t_map_point_2d  offset;
	int const*		ptr = footprint.get();
	double			value;
	double			result = 0.0;

	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			value = map.get( point + offset );
			if (result > value)
				result = value;
		}
	}
	return result;
}

double t_ai_combat_data_cache::get_influence_weight( t_map_point_2d const& point )
{
	if (!m_influence_map_valid)
		create_influence_map();

	t_battlefield&				battlefield = *m_battlefield;
	t_combat_creature const&	acting_creature = *battlefield.get_acting_creature();
	double						result;
	int							total_hits = acting_creature.get_total_hits();
	double						total_value = acting_creature.get_ai_value( total_hits );

	result = get_lowest_value( m_influence_map, acting_creature.get_footprint(), point );
	if (result < -total_value)
		result = -total_value;
	return result;
}

// ---------------------------------------------------------------
// get most devestating area effect attack by creature
// ---------------------------------------------------------------
static double get_area_effect_weight( t_battlefield&			battlefield,
									  t_combat_creature const&	attacker,
									  t_combat_creature const&	target )
{
	double result = 0.0;

	// normal attack is area effect
	if (attacker.has_ability( k_ability_area_effect ) && battlefield.can_shoot( attacker ))
	{
		int	damage;

		damage = attacker.get_ranged_damage( target, 0, 0 ) * attacker.get_attacks( true );
		result = target.get_ai_value( damage );
	}
	if (attacker.can_cast_spells())
	{
		static t_spell const	k_area_spells[] = 
		{ k_spell_fireball, k_spell_inferno, k_spell_fire_ring };
		int						i;
		t_spell					spell;
		int						damage;
		double					value = 0.0;
		
		for (i = 0; i < ELEMENTS_OF( k_area_spells ); ++i)
		{
			spell = k_area_spells[i];
			if (!attacker.can_cast( spell ))
				continue;
			if (!can_affect( attacker, spell, target ))
				continue;
			damage = attacker.get_spell_damage( target, spell );
			value = target.get_ai_value( damage );
			if (result < value)
				result = value;
		}
	}
	return result;
}


// ---------------------------------------------------------------
// mark areas in a footprint
// ---------------------------------------------------------------
static void mark_footprint( t_combat_footprint const&	footprint,
						    t_map_point_2d const&		point,
						    t_influence_map&			map,
							t_isometric_map<int>&		marked,
							double						weight,
							double						reduced_weight )
{
	int				footprint_size = footprint.get_size();
	t_map_point_2d	offset;
	int const*		ptr = footprint.get();
	t_map_point_2d	new_point;

	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = point + offset;
			if (!map.is_valid( new_point ))
				continue;
			if (marked.get( new_point ))
				map.get( new_point ) += reduced_weight;
			else
			{
				marked.get( new_point ) = true;
				map.get( new_point ) += weight;
			}
		}
	}
}

// ---------------------------------------------------------------
// mark circles to exclude areas around friendly creatures which
// might result in an area effect attack
// ---------------------------------------------------------------
static void mark_circles( t_battlefield&			battlefield,
						  t_influence_map&			map, 
						  t_combat_creature const&	current_creature,
						  double					weight,
						  int						breath_range,
						  int						minimum_distance )
{
	t_combat_creature const*				creature;
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	int										distance;
	int										footprint_size;
	double									reduced_weight = weight * 0.1;
	t_map_point_2d							point;
	t_isometric_map<int>					marked( battlefield.get_size(), k_battlefield_cell_height, 
													k_battlefield_logical_view_size, 0 );

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->get_controller() != current_creature.get_controller())
			continue;
		if (creature == &current_creature)
			continue;

		distance = breath_range - creature->get_footprint_size();
		if (distance < minimum_distance)
			distance = minimum_distance;
		point = creature->get_cell_position();
		point.row -= distance;
		point.column -= distance;
		footprint_size = creature->get_footprint_size() + distance * 2;

		t_combat_footprint const&	footprint = get_combat_footprint( footprint_size );

		mark_footprint( footprint, point, map, marked, weight, reduced_weight );
	}
}

// ---------------------------------------------------------------
// mark all area effects
// ---------------------------------------------------------------
static void mark_area_effects( t_battlefield&			battlefield,
							   t_influence_map&			map, 
							   t_combat_creature const& current_creature,
							   t_ai_combat_data_cache&	data )
{
	t_combat_creature const*				enemy;
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	double									weight;

	for (; index != end; ++index)
	{
		enemy = *index;
		if (enemy->get_controller() == current_creature.get_controller())
			continue;
		if (!enemy->is_awake())
			continue;
		if (enemy->is_active( k_spell_song_of_peace ))
			continue;

		weight = -get_area_effect_weight( battlefield, *enemy, current_creature );
		if (weight < 0.0)
			mark_circles( battlefield, map, current_creature, weight, 0, 6 );
		if (enemy->has_ability( k_ability_breath_attack ))
		{
			int minimum_distance = k_breath_range - current_creature.get_footprint_size();
			int distance = k_breath_range;
			int damage;

			// "minimum distance" assumes dragon breathes through current creature to hit target.
			// "distance" assumes dragon breathes through other creature to hit current creature.
			if (current_creature.has_ability( k_ability_fire_resistance ))
				distance = 0;
			damage = enemy->get_melee_damage( current_creature, enemy->get_combat_movement() )
					* enemy->get_attacks( false );
			weight = -current_creature.get_ai_value( damage );
			mark_circles( battlefield, map, current_creature, weight, distance, minimum_distance );
		}
	}
}

// ---------------------------------------------------------------
// mark multi-headed attacks
// ---------------------------------------------------------------
static void mark_multi_headed_attacks( t_battlefield&			battlefield,
									   t_influence_map&			map, 
									   t_combat_creature const& current_creature,
									   t_combat_creature const& enemy,
									   double					weight,
									   t_ai_combat_data_cache&	data )
{
	t_combat_creature const*				creature;
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	t_map_point_2d							point;
	t_direction								direction;
	int										movement = enemy.get_combat_movement();
	int										i;
	int										attack_distance = enemy.get_attack_range() + 2;
	int										arc = enemy.get_arc_attack();
	int										footprint_size = attack_distance * 2 
															+ enemy.get_footprint_size();
	t_attack_angle_list						attack_angles;
	t_isometric_map<int>					marked( battlefield.get_size(), k_battlefield_cell_height, 
													k_battlefield_logical_view_size, 0 );

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->get_controller() != current_creature.get_controller())
			continue;
		if (creature == &current_creature)
			continue;
		attack_angles = data.get_attack_angles( enemy, *creature );
		if (attack_angles.empty())
			continue;
		if (attack_angles.front().move_distance > movement)
			continue;
		for (i = 0; i < attack_angles.size(); ++i)
		{
			direction = get_direction( attack_angles[i].attack_angle );

			t_threat_footprint const& footprint 
				= get_threat_footprint( footprint_size, direction, arc );

			point = attack_angles[i].point;
			point.row -= attack_distance;
			point.column -= attack_distance;
			mark_footprint( footprint, point, map, marked, weight, 0.0 );
		}
	}
}

// ---------------------------------------------------------------
// mark multi-headed attacks
// ---------------------------------------------------------------
static void mark_all_multi_headed_attacks( t_battlefield&			battlefield,
										   t_influence_map&			map, 
										   t_combat_creature const& current_creature,
									   	   t_ai_combat_data_cache&	data )
{
	t_combat_creature const*				enemy;
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	int										damage;
	double									weight;

	for (; index != end; ++index)
	{
		enemy = *index;
		if (enemy->get_controller() == current_creature.get_controller())
			continue;
		if (!enemy->is_awake())
			continue;
		if (enemy->is_active( k_spell_song_of_peace ))
			continue;
		if (!enemy->has_ability( k_ability_hydra_strike ) 
			&& !enemy->has_ability( k_ability_3_headed_attack ))
			continue;

		damage = enemy->get_melee_damage( current_creature, enemy->get_combat_movement() )
				* enemy->get_attacks( false );
		weight = -current_creature.get_ai_value( damage );
		mark_multi_headed_attacks( battlefield, map, current_creature, *enemy, weight, data );
	}
}


// ---------------------------------------------------------------
// create an influence map
// ---------------------------------------------------------------
void t_ai_combat_data_cache::create_influence_map()
{
	if (m_influence_map_valid)
		return;

	t_battlefield&				battlefield = *m_battlefield;
	t_combat_creature const*	current_creature = battlefield.get_acting_creature();

	m_influence_map_valid = true;
	if (m_influence_map.get_size() == 0)
	{
		m_influence_map.initialize( battlefield.get_size(), k_battlefield_cell_height, 
									k_battlefield_logical_view_size );
	}
	
	// clear the influence map
	t_map_point_2d	point;
	int				row_size;
	double*			ptr;

	point.row = m_influence_map.get_size();
	while (point.row--)
	{
		point.column = m_influence_map.get_row_start( point.row );
		row_size = m_influence_map.get_row_size( point.row );
		ptr = &m_influence_map.get( point );
		while (row_size--)
		{
			*ptr++ = 0.0;
		}
	}

	if (battlefield.get_difficulty() < k_difficulty_hard)
		return;

	// mark melee ranges for enemies
	mark_melee_ranges( *m_battlefield, m_influence_map, *current_creature, *this );
	// mark area effect attacks
	mark_area_effects( *m_battlefield, m_influence_map, *current_creature, *this );
	// mark hydra-type attacks
	mark_all_multi_headed_attacks( *m_battlefield, m_influence_map, *current_creature, *this );
}
